package Algorithm.Sort;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * 快速排序的基本思想：
 * 通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，
 * 则可分别对这两部分记录继续进行排序，以达到整个序列有序。
 */
public class QuickSort {
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * 快速排序
     *
     * @param arr
     */
    public static void quickSort(int[] arr) {
        quickSortInternal(arr, 0, arr.length - 1);
    }

    /**
     * 在arr[l..r]上进行快速排序
     *
     * @param arr
     * @param l
     * @param r
     */
    private static void quickSortInternal(int[] arr, int l, int r) {
        if (l > r) {
            return;
        }
        // 先获取分区点
        // 所谓的分区点就是经过分区函数后，某个元素落在了最终的位置
        // 分区点左侧全都是小于该元素的区间，分区点右侧全都是 >= 该元素的区间
        int p = partition(arr, l, r);
        // 重复在左区间和右区间上重复上述流程
        quickSortInternal(arr, l, p - 1);
        quickSortInternal(arr, p + 1, r);
    }

    /**
     * 在arr[l..r]上的分区函数，返回分区点的索引
     *
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int partition(int[] arr, int l, int r) {
//        // 随机在当前数组中选一个数
//        ThreadLocalRandom random=ThreadLocalRandom.current();
//        int randomIndex = random.nextInt(l,r);
//        swap(arr,l,randomIndex);
        int v = arr[l];
        // arr[l + 1..j] < v
        // arr[j + 1..i) >= v
        // i表示当前正在扫描的元素
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] < v) {
                swap(arr, j + 1, i);
                j++;
            }
        }
        // 将基准值和最后一个 < v的元素交换，基准值就落在了最终位置
        swap(arr, l, j);
        return j;
    }

    /**
     * 借助栈来实现非递归分治快排
     *
     * @param arr
     */
    public static void quickSortNonRecursion(int[] arr) {
        Deque<Integer> stack = new ArrayDeque<>();
        // 栈中保存当前集合的开始位置和终止位置
        int l = 0;
        int r = arr.length - 1;
        stack.push(r);
        stack.push(l);
        while (!stack.isEmpty()) {
            // 栈不为空时，说明子区间还没有处理完毕
            int left = stack.pop();
            int right = stack.pop();
            if (left >= right) {
                // 区间只有一个元素
                continue;
            }
            int p = partition(arr, left, right);
            // 依次将右区间的开始和结束位置入栈
            stack.push(right);
            stack.push(p + 1);
            // 再将左侧区间的开始和结束位置入栈
            stack.push(p - 1);
            stack.push(left);
        }
    }

    public static void main(String[] args) {
        int[] arr2 = {9, 1, 5, 8, 3, 7, 4, 6, 2};
        quickSort(arr2);
        System.out.println(Arrays.toString(arr2));
    }
}
